package org.example.day02;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO +
 * 部门在进行需求开发时需要进行人力安排。当前部门需要完成N个需求，需求用requirements[]表示，requirements[i]表示第i个需求的工作量大小，单位：人月。<br> 这部分需求需要在M个月内完成开发，进行人力安排后每个月的人力是固定的。<br> <br> 目前要求每个月最多有2个需求开发，并且每个月需要完成的需求不能超过部门人力。请帮部门评估在满足需求开发进度的情况下，<br> 每个月需要的最小人力是多少？<br>
 *
 * 部门在进行需求开发时需要进行人力安排。当前部门需要完成N个需求，
 * 需求用requirements[]表示，requirements[i]表示第i个需求的工作量大小，单位：人月。
 * 这部分需求需要在M个月内完成开发，进行人力安排后每个月的人力是固定的。
 * 目前要求每个月最多有2个需求开发，并且每个月需要完成的需求不能超过部门人力。
 * 请帮部门评估在满足需求开发进度的情况下， 每个月需要的最小人力是多少？
 * @date 2024/3/11 15:22
 */
public class test032 {

    // 检查给定人力是否可以按时完成工作的辅助方法
    private static boolean canFinishOnTime(int[] requirements, int m, int manpower) {
        int left = 0, right = requirements.length - 1; // 使用双指针技术
        int requiredMonths = 0; // 需要的月份

        // 遍历需求，尝试匹配
        while (left <= right) {
            if (left == right || requirements[left] + requirements[right] <= manpower) {
                left++;
            }
            right--;
            requiredMonths++;
        }

        return requiredMonths <= m; // 检查是否可以在限定时间内完成
    }

    // 计算最小人力需求的函数
    public static int calculateMinimumManpower(int m, int[] requirements) {
        Arrays.sort(requirements); // 对需求工作量进行排序

        int minManpower = Arrays.stream(requirements).max().getAsInt(); // 确定人力范围的最小值
        int maxManpower = Arrays.stream(requirements).sum(); // 确定人力范围的最大值

        // 二分搜索寻找最小人力
        while (minManpower < maxManpower) {
            int midManpower = (minManpower + maxManpower) / 2;
            if (canFinishOnTime(requirements, m, midManpower)) {
                maxManpower = midManpower;
            } else {
                minManpower = midManpower + 1;
            }
        }

        return minManpower; // 返回最小人力需求
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int m = scanner.nextInt(); // 读取开发时间要求
        scanner.nextLine(); // 读取换行符
        String[] input = scanner.nextLine().split(" "); // 读取需求工作量字符串并分割
        int[] requirements = Arrays.stream(input).mapToInt(Integer::parseInt).toArray(); // 将字符串数组转换为整数数组

        System.out.println(calculateMinimumManpower(m, requirements)); // 打印最小人力需求
    }
}

